package jCross.intel;

import java.util.Arrays;

import jCross.io.IOUtil;

public class Solver {
	static int[][] data = null;
	static int[][] upData = null;
	static int[][] leftData = null;
	
	/**
	 * supposed to keep the information in the following way:
	 * for upData[i][j] block, the upMinIndex[i][j] - is the minimum top point ordinate, and upMaxIndex[i][j] - the maximum of bottom point of the block.
	 */
	static int[][] upMinIndex = null, upMaxIndex = null, leftMinIndex = null, leftMaxIndex = null;
	
	static boolean vb = false, hasProblems = false, printProblems = true;
	
	public static void solve() {
		data = TableData.getInstance().data;
		upData = IOUtil.upLevels;
		leftData = IOUtil.leftLevels;
		
		initIndexes();
		
		basicImprove();
		
		complexImprove();
	}
	
	public static void basicImprove() {
		vb = true;
		while(vb) {
			vb = false;
			
			for(int i = 0; i < data.length; i++) {
				for(int j = 0; j < data[i].length; j++) {
					if(data[i][j] != TableData.EMPTY) {
						continue;
					}
					if(!canBeCheck(i, j)) {
						data[i][j] = TableData.UNCHECK;
						// update min and max block indexes
						updateMinMaxUncheck(i, j);
						vb = true;
					} else if(!canBeUncheck(i, j)) {
						data[i][j] = TableData.CHECK;
						// update min and max block indexes
						updateMinMaxCheck(i, j);
						vb = true;
					}
				}
			}
			for(int i = 0; i < data.length; i++) {
				for(int j = 0; j < data[i].length; j++) {
					if(data[i][j] == TableData.UNCHECK) {
						updateMinMaxUncheck(i, j);
					}
					if(data[i][j] == TableData.CHECK) {
						updateMinMaxCheck(i, j);
					}
				}
			}
			normalizeMinMaxIndexes();
		}
	}

	public static void complexImprove() {
		printProblems = false;
		hasProblems = false;
		int[][] dataBackup = new int[IOUtil.wd][IOUtil.ht],
			upMinBackup = new int[upMinIndex.length][], upMaxBackup = new int[upMaxIndex.length][],
			leftMinBackup = new int[leftMinIndex.length][], leftMaxBackup = new int[leftMaxIndex.length][];
		copyData(new int[][][] {data, upMinIndex, upMaxIndex, leftMinIndex, leftMaxIndex}, new int[][][] {dataBackup, upMinBackup, upMaxBackup, leftMinBackup, leftMaxBackup});
		
		boolean tryChanges = true;
		while(tryChanges) {
			tryChanges = false;
			int tot = 0;
			for(int x = 0; x < dataBackup.length; x++) {
				for(int y = 0; y < dataBackup[x].length; y++) {
					if(data[x][y] == TableData.EMPTY) {
						tot++;
						data[x][y] = TableData.CHECK;
						basicImprove();
						copyData(new int[][][] {dataBackup, upMinBackup, upMaxBackup, leftMinBackup, leftMaxBackup}, new int[][][] {data, upMinIndex, upMaxIndex, leftMinIndex, leftMaxIndex});
						if(hasProblems) {
							tryChanges = true;
							hasProblems = false;
							data[x][y] = TableData.UNCHECK;
							basicImprove();
							copyData(new int[][][] {data, upMinIndex, upMaxIndex, leftMinIndex, leftMaxIndex}, new int[][][] {dataBackup, upMinBackup, upMaxBackup, leftMinBackup, leftMaxBackup});
							if(hasProblems) {
								System.out.println("WTF 1");
							}
							break;
						}
						data[x][y] = TableData.UNCHECK;
						basicImprove();
						copyData(new int[][][] {dataBackup, upMinBackup, upMaxBackup, leftMinBackup, leftMaxBackup}, new int[][][] {data, upMinIndex, upMaxIndex, leftMinIndex, leftMaxIndex});
						if(hasProblems) {
							tryChanges = true;
							hasProblems = false;
							data[x][y] = TableData.CHECK;
							basicImprove();
							copyData(new int[][][] {data, upMinIndex, upMaxIndex, leftMinIndex, leftMaxIndex}, new int[][][] {dataBackup, upMinBackup, upMaxBackup, leftMinBackup, leftMaxBackup});
							if(hasProblems) {
								System.out.println("WTF 2");
							}
							break;
						}
					}
				}
			}
			System.out.println("tot = " + tot);
		}
	}
	
	private static boolean canBeCheck(int x, int y) {
		boolean upPossible = false, leftPossible = false;
		
		int rightNr = 1;
		while(x + rightNr < data.length && data[x + rightNr][y] == TableData.CHECK) {
			rightNr++;
		}
		int leftNr = 1;
		while(x - leftNr >= 0 && data[x - leftNr][y] == TableData.CHECK) {
			leftNr++;
		}
		int downNr = 1;
		while(y + downNr < data[x].length && data[x][y + downNr] == TableData.CHECK) {
			downNr++;
		}
		int upNr = 1;
		while(y - upNr >= 0 && data[x][y - upNr] == TableData.CHECK) {
			upNr++;
		}
		
		boolean isTmpOk = false;
		for(int i = 0; i < upData[x].length && !isTmpOk; i++) {
			if(upMinIndex[x][i] <= y && upMaxIndex[x][i] >= y && upNr + downNr - 1 <= upData[x][i]) {
				isTmpOk =  true;
				break;
			}
		}
		if(!isTmpOk) {
			return false;
		}
		isTmpOk = false;
		for(int i = 0; i < leftData[y].length && !isTmpOk; i++) {
			if(leftMinIndex[y][i] <= x && leftMaxIndex[y][i] >= x && leftNr + rightNr - 1 <= leftData[y][i]) {
				isTmpOk =  true;
				break;
			}
		}
		if(!isTmpOk) {
			return false;
		}

		// check the up thing
		int minInd = 0, maxInd = IOUtil.ht - 1, totNecesary = upData[x].length - 1;
		
		for(int i = 0; i < upData[x].length; i++) {
			totNecesary += upData[x][i];
		}
		
		maxInd -= totNecesary;
		
		for(int i = 0; i < upData[x].length && !upPossible; i++) {
			if(y < minInd) {
				break;
			}

			int val = upData[x][i], min = minInd, max = maxInd + val;
			minInd += val + 1;
			maxInd += val + 1;
			
			if(y > max) {
				continue;
			}
			
			for(int j = 0; j < val; j++) {
				if(min + j > y) {
					break;
				}
				if(y > max - val + 1 + j) {
					continue;
				}
				if(y - j - 1 >= 0 && data[x][y - j - 1] == TableData.CHECK) {
					continue;
				}
				boolean isOk = true;
				for(int k = 0; k < j; k++) {
					if(data[x][y + k - j] == TableData.UNCHECK) {
						isOk = false;
						break;
					}
				}
				if(isOk) {
					upPossible = true;
					break;
				}
			}
		}
		
		// check the left thing
		minInd = 0;
		maxInd = IOUtil.wd - 1;
		totNecesary = leftData[y].length - 1;
		
		for(int i = 0; i < leftData[y].length; i++) {
			totNecesary += leftData[y][i];
		}
		
		maxInd -= totNecesary;

		for(int i = 0; i < leftData[y].length && !leftPossible; i++) {
			if(x < minInd) {
				break;
			}

			int val = leftData[y][i], min = minInd, max = maxInd + val;
			minInd += val + 1;
			maxInd += val + 1;
			
			if(x > max) {
				continue;
			}
			
			for(int j = 0; j < val; j++) {
				if(min + j > x) {
					break;
				}
				if(x > max - val + 1 + j) {
					continue;
				}
				if(x - j - 1 >= 0 && data[x - j - 1][y] == TableData.CHECK) {
					continue;
				}
				boolean isOk = true;
				for(int k = 0; k < j; k++) {
					if(data[x + k - j][y] == TableData.UNCHECK) {
						isOk = false;
						break;
					}
				}
				if(isOk) {
					leftPossible = true;
					break;
				}
			}
		}
		
		return upPossible && leftPossible;
	}

	/**
	 * 
	 * @param x - x coordinate
	 * @param y - y coordinate
	 * @return if possible to be empty the slot in this cell
	 */
	private static boolean canBeUncheck(int x, int y) {
		for(int i = 0; i < upData[x].length; i++) {
			if(upMinIndex[x][i] <= y && upMaxIndex[x][i] >= y && y - upMinIndex[x][i] < upData[x][i] && upMaxIndex[x][i] - y < upData[x][i]) {
				return false;
			}
		}
		for(int i = 0; i < leftData[y].length; i++) {
			if(leftMinIndex[y][i] <= x && leftMaxIndex[y][i] >= x && x - leftMinIndex[y][i] < leftData[y][i] && leftMaxIndex[y][i] - x < leftData[y][i]) {
				return false;
			}
		}

		boolean upPossible = false, leftPossible = false;
		
		// check the up thing
		int minInd = 0, maxInd = IOUtil.ht - 1, totNecesary = upData[x].length - 1;
		
		for(int i = 0; i < upData[x].length; i++) {
			totNecesary += upData[x][i];
		}
		
		maxInd -= totNecesary;
		
		if(y <= maxInd) {
			upPossible = true;
		}
		for(int i = 0; i < upData[x].length && !upPossible; i++) {
			int val = upData[x][i];
			minInd += val + 1;
			maxInd += val + 1;

			if(y < minInd - 1) {
				break;
			}
			
			if(y > maxInd) {
				continue;
			}
			upPossible = true;
			break;
		}
		
		// check the left thing
		minInd = 0;
		maxInd = IOUtil.wd - 1;
		totNecesary = leftData[y].length - 1;
		
		for(int i = 0; i < leftData[y].length; i++) {
			totNecesary += leftData[y][i];
		}
		
		maxInd -= totNecesary;
		
		if(x <= maxInd) {
			leftPossible = true;
		}
		for(int i = 0; i < leftData[y].length && !leftPossible; i++) {
			int val = leftData[y][i];
			minInd += val + 1;
			maxInd += val + 1;
			
			if(x < minInd - 1) {
				break;
			}
			if(x > maxInd) {
				continue;
			}
			leftPossible = true;
			break;
		}
		return upPossible && leftPossible;
	}
	
	static void initIndexes() {
		upMinIndex = new int[upData.length][];
		upMaxIndex = new int[upData.length][];
		leftMinIndex = new int[leftData.length][];
		leftMaxIndex = new int[leftData.length][];
		for(int i = 0; i < upData.length; i++) {
			upMinIndex[i] = new int[upData[i].length];
			upMaxIndex[i] = new int[upData[i].length];
			Arrays.fill(upMaxIndex[i], leftData.length - 1);
		}
		for(int i = 0; i < leftData.length; i++) {
			leftMinIndex[i] = new int[leftData[i].length];
			leftMaxIndex[i] = new int[leftData[i].length];
			Arrays.fill(leftMaxIndex[i], upData.length - 1);
		}

		for(int i = 0; i < upData.length; i++) {
			int min = 0;
			for(int j = 0; j < upData[i].length; j++) {
				upMinIndex[i][j] = min;
				min += upData[i][j] + 1;
			}
			int max = leftData.length - 1;
			for(int j = upData[i].length - 1; j >= 0; j--) {
				upMaxIndex[i][j] = max;
				max -= upData[i][j] + 1;
			}
		}
		for(int i = 0; i < leftData.length; i++) {
			int min = 0;
			for(int j = 0; j < leftData[i].length; j++) {
				leftMinIndex[i][j] = min;
				min += leftData[i][j] + 1;
			}
			int max = upData.length - 1;
			for(int j = leftData[i].length - 1; j >= 0; j--) {
				leftMaxIndex[i][j] = max;
				max -= leftData[i][j] + 1;
			}
		}
	}
	
	static void updateMinMaxUncheck(int i, int j) {
		for(int k = 0; k < upData[i].length; k++) {
			if(upMinIndex[i][k] <= j && upMaxIndex[i][k] >= j) {
				if(j - upMinIndex[i][k] < upData[i][k]) {
					upMinIndex[i][k] = j + 1;
					vb = true;
				}
				if(upMaxIndex[i][k] - j < upData[i][k]) {
					upMaxIndex[i][k] = j - 1;
					vb = true;
				}
				if(upMaxIndex[i][k] - upMinIndex[i][k] + 1 < upData[i][k]) {
					hasProblems = true;
					if(printProblems) {
						System.out.println("ERROR 1 " + i + "-" + k);
					}
				}
			}
		}
		for(int k = 0; k < leftData[j].length; k++) {
			if(leftMinIndex[j][k] <= i && leftMaxIndex[j][k] >= i) {
				if(i - leftMinIndex[j][k] < leftData[j][k]) {
					leftMinIndex[j][k] = i + 1;
					vb = true;
				}
				if(leftMaxIndex[j][k] - i < leftData[j][k]) {
					leftMaxIndex[j][k] = i - 1;
					vb = true;
				}
				if(leftMaxIndex[j][k] - leftMinIndex[j][k] + 1 < leftData[j][k]) {
					hasProblems = true;
					if(printProblems) {
						System.out.println("ERROR 2 " + j + "-" + k);
					}
				}
			}
		}
	}

	static void updateMinMaxCheck(int i, int j) {
		for(int k = 0; k < upData[i].length; k++) {
			if(upMinIndex[i][k] <= j && upMaxIndex[i][k] >= j && upMaxIndex[i][k] - j <= upData[i][k] && j - upMinIndex[i][k] <= upData[i][k]) {
				// means i, j is certainly mapped to upData[i][k], so we exclude possible corners and upMin/upMax around
				if(j - upMinIndex[i][k] == upData[i][k]) {
					upMinIndex[i][k]++;
					vb = true;
				}
				if(upMaxIndex[i][k] - j == upData[i][k]) {
					upMaxIndex[i][k]--;
					vb = true;
				}
			}
			if(upMinIndex[i][k] <= j && upMaxIndex[i][k] >= j &&
					(k == 0 || upMaxIndex[i][k - 1] < j) &&
					(k + 1 == upData[i].length || upMinIndex[i][k + 1] > j)) {
				if(j - upMinIndex[i][k] >= upData[i][k]) {
					upMinIndex[i][k] = j - upData[i][k] + 1;
					vb = true;
				}
				if(upMaxIndex[i][k] - j >= upData[i][k]) {
					upMaxIndex[i][k] = j + upData[i][k] - 1;
					vb = true;
				}
			}
		}
		for(int k = 0; k < leftData[j].length; k++) {
			if(leftMinIndex[j][k] <= i && leftMaxIndex[j][k] >= i && leftMaxIndex[j][k] - i <= leftData[j][k] && i - leftMinIndex[j][k] <= leftData[j][k]) {
				// means i, j is certainly mapped to leftData[i][k], so we exclude possible corners and leftMin/leftMax around
				if(i - leftMinIndex[j][k] == leftData[j][k]) {
					leftMinIndex[j][k]++;
					vb = true;
				}
				if(leftMaxIndex[j][k] - i == leftData[j][k]) {
					leftMaxIndex[j][k]--;
					vb = true;
				}
			}
			if(leftMinIndex[j][k] <= i && leftMaxIndex[j][k] >= i &&
					(k == 0 || leftMaxIndex[j][k - 1] < i) &&
					(k + 1 == leftData[j].length || leftMinIndex[j][k + 1] > i)) {
				if(i - leftMinIndex[j][k] >= leftData[j][k]) {
					leftMinIndex[j][k] = i - leftData[j][k] + 1;
					vb = true;
				}
				if(leftMaxIndex[j][k] - i >= leftData[j][k]) {
					leftMaxIndex[j][k] = i + leftData[j][k] - 1;
					vb = true;
				}
			}
		}
	}
	
	static void normalizeMinMaxIndexes() {
		for(int i = 0; i < upData.length; i++) {
			for(int j = 0; j < upData[i].length; j++) {
				if(j > 0 && upMinIndex[i][j] - upMinIndex[i][j - 1] <= upData[i][j - 1]) {
					upMinIndex[i][j] = upMinIndex[i][j - 1] + upData[i][j - 1] + 1;
					vb = true;
				}
				if(j + 1 < upData[i].length && upMaxIndex[i][j + 1] - upMaxIndex[i][j] <= upData[i][j + 1]) {
					upMaxIndex[i][j] = upMaxIndex[i][j + 1] - upData[i][j + 1] - 1;
					vb = true;
				}
			}
		}
		for(int i = 0; i < leftData.length; i++) {
			for(int j = 0; j < leftData[i].length; j++) {
				if(j > 0 && leftMinIndex[i][j] - leftMinIndex[i][j - 1] <= leftData[i][j - 1]) {
					leftMinIndex[i][j] = leftMinIndex[i][j - 1] + leftData[i][j - 1] + 1;
					vb = true;
				}
				if(j + 1 < leftData[i].length && leftMaxIndex[i][j + 1] - leftMaxIndex[i][j] <= leftData[i][j + 1]) {
					leftMaxIndex[i][j] = leftMaxIndex[i][j + 1] - leftData[i][j + 1] - 1;
					vb = true;
				}
			}
		}
	}
	
	private static void copyData(int[][][] from, int[][][] to) {
		for(int a = 0; a < from.length; a++) {
			for(int i = 0; i < from[a].length; i++) {
				if(to[a][i] == null) {
					to[a][i] = new int[from[a][i].length];
				}
				for(int j = 0; j < from[a][i].length; j++) {
					to[a][i][j] = from[a][i][j];
				}
			}
		}
	}
}
